package 所有的题类.F.树;

import 所有的题类.ZA.链表.TreeNode;

public class 二叉树的直径 {
    /**
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
     * 示例 :
     * 给定二叉树
     *
     *           1
     *          / \
     *         2   3
     *        / \
     *       4   5
     * 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    public void diameterOfBinaryTree(TreeNode root) {
        //首先我们知道一条路径的长度为该路径经过的节点数减一


        //1：理解题意
        //2：解析思路（先求深度再求路径（深度-1)
            //1)维护一个全局变量为做大的节点数（二叉树上任意两个节点之间的最大的数量）
            //2)编写递归算法，返回节点数量
            //3)编写递归的终止条件，当节点为空返回0
            //4)递归左子树
            //5)递归右子树
            //6)**重要比较 得到当前root左右子树的节点数量L+R+1
            //7)与全局的节点数量做比较，比较的时候要L+R+1跟asn去比较，返回的时候还要比较L,R,
            //并且将结果集+1,代表深度
    }
}
